#include <iostream>
#include <vector>

using namespace std;

// Q2. 相邻字符串之间的最长公共前缀
// https://leetcode.cn/contest/weekly-contest-456/problems/longest-common-prefix-between-adjacent-strings-after-removals/description/

class Solution
{
public:
    int earnMaxPreLen(string &s1, string &s2)
    {
        int ans = 0;
        for (int i = 0; i < s1.size() && i < s2.size(); i++)
        {
            if (s1[i] == s2[i])
            {
                ans++;
                continue;
            }
            break;
        }
        return ans;
    }
    vector<int> longestCommonPrefix(vector<string> &words)
    {
        int n = words.size();
        vector<int> ans(n);
        vector<int> rightMaxPreLen(n);
        int maxLen = 0;
        for (int i = 2; i < words.size(); i++)
        {
            maxLen = max(maxLen, earnMaxPreLen(words[i - 1], words[i - 2]));
            rightMaxPreLen[i] = maxLen;
        }
        vector<int> leftMaxPreLen(n);
        maxLen = 0;
        for (int i = n - 3; i >= 0; --i)
        {
            maxLen = max(maxLen, earnMaxPreLen(words[i + 2], words[i + 1]));
            leftMaxPreLen[i] = maxLen;
        }
        int curLen = 0;
        for (int i = 0; i < n; i++)
        {
            if(i > 0 && i < n - 1){
                curLen = earnMaxPreLen(words[i - 1], words[i + 1]);
            }
            ans[i] = max(max(rightMaxPreLen[i], leftMaxPreLen[i]), curLen);
            curLen = 0;
        }
        return ans;
    }
};

int main()
{
    return 0;
}